package leetcode;

import java.util.HashMap;

/**
 * @Project : algorithm-learning-java
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/6 12:47
 */
public class Q0525 {
    /**
     * O(n^2) O(1)
     */
//    public int findMaxLength(int[] nums) {
//        if (nums.length < 2) return 0;
//        int res = 0;
//        int tmp = 0;
//        for (int i = 0; i < nums.length - 1; i++) {
//            for (int j = i; j < nums.length; j++) {
//                if (i == j) {
//                    tmp = nums[i];
//                } else {
//                    tmp += nums[j];
//                    if (j - i + 1 == 2 * tmp) res = Math.max(res, tmp * 2);
//                }
//            }
//        }
//        return res;
//    }

    /**
     * O(n) O(n)
     */
    // 前缀和 + hashmap
    public int findMaxLength(int[] nums) {
        if (nums.length < 2) return 0;
        int res = 0;
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + (nums[i] == 0 ? -1 : 1);
        }

        for (int i = 0; i < sum.length; i++) {
            if (!map.containsKey(sum[i])) {
                map.put(sum[i], i);
                continue;
            }
            res = Math.max(res, i - map.get(sum[i]));
        }

        return res;
    }
}
